﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Teal.Compiler {

    /// <summary>
    /// 表示一个简单的单链表。
    /// </summary>
    public sealed class SingleLinkedList<T> : IEnumerable<T>
        where T : SingleLinkedListNode {

        /// <summary>
        /// 存储当前单链表的最后一个节点。它的 next 指向第一个节点。
        /// </summary>
        T _lastNode;

        public T first {
            get {
                return _lastNode == null ? null : (T)_lastNode.next;
            }
        }

        public T last {
            get {
                return _lastNode;
            }
        }

        public bool isEmpty {
            get {
                return _lastNode == null;
            }
        }

        public bool notEmpty {
            get {
                return _lastNode != null;
            }
        }

        public int length {
            get {
                if (_lastNode == null) {
                    return 0;
                }
                int sum = 1;
                for (SingleLinkedListNode n = _lastNode; n != _lastNode; n = n.next) {
                    sum++;
                }
                return sum;
            }
        }

        public void addLast(T value) {

            Debug.Assert(value.next == null, "当前节点已被添加到其它节点，无法重复添加");

            // 第一个节点，创建自己的循环引用。
            if (_lastNode == null) {
                _lastNode = value;
                value.next = value;
                return;
            }

            // 更新新节点的 next 为第一个节点，然后更新最后一个节点。
            value.next = _lastNode.next;
            _lastNode.next = value;
            _lastNode = value;
        }

        public void addFirst(T value) {

            Debug.Assert(value.next == null, "当前节点已被添加到其它节点，无法重复添加");

            // 第一个节点，创建自己的循环引用。
            if (_lastNode == null) {
                _lastNode = value;
                value.next = value;
                return;
            }

            value.next = _lastNode.next.next;
            _lastNode.next = value;
        }

        public void addAfter(T refValue, T value) {

            Debug.Assert(value.next == null, "当前节点已被添加到其它节点，无法重复添加");

            value.next = refValue.next;
            refValue.next = value;
        }

        public void add(T value) {
            addLast(value);
        }

        T getBefore(T refValue) {

            Debug.Assert(refValue.next == null, "当前节点已被添加到其它节点，无法重复添加");

            SingleLinkedListNode before = _lastNode;
            while (before.next != refValue && before.next != _lastNode) {
                before = before.next;
            }
            return (T)before;
        }

        public void addBefore(T refValue, T value) {
            addAfter(getBefore(refValue), value);
        }

        public void remove(T value) {
            if (_lastNode == null || _lastNode == _lastNode.next) {
                if (value == _lastNode) {
                    _lastNode = null;
                    value.next = null;
                }
                return;
            }

            getBefore(value).next = value.next;
            value.next = null;
        }

        struct Enumerator : IEnumerator<T> {

            SingleLinkedListNode _currentNode;

            SingleLinkedListNode _lastNode;

            public Enumerator(T lastNode) {

                round = false;
                _currentNode = _lastNode = lastNode;

                // 没有任何节点，特殊优化。
                if (lastNode == null) {
                    round = true;
                }

            }

            public T Current {
                get {
                    return (T)_currentNode;
                }
            }

            public void Dispose() {

            }

            object System.Collections.IEnumerator.Current {
                get {
                    return _currentNode;
                }
            }

            bool round;

            public bool MoveNext() {

                // 如果之前已经移动最后一个节点，则第2次以后不再循环。
                if (_currentNode == _lastNode) {
                    if (round) {
                        return false;
                    }
                    round = true;
                }

                _currentNode = _currentNode.next;

                return true;
            }

            public void Reset() {
                _currentNode = _lastNode;
                round = false;
            }
        }

        public IEnumerator<T> GetEnumerator() {
            return new Enumerator(_lastNode);
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }
    }

    /// <summary>
    /// 表示单链表中的一个子节点。
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class SingleLinkedListNode {

        /// <summary>
        /// 支持多个对象组成一个单链表。
        /// </summary>
        public SingleLinkedListNode next;

    }

}